using System;

namespace LeetCode {
    public class LongestPalindrome {
        public int LongestPalindromeSubseq (string s) {
            char[] chars = s.ToCharArray ();
            int length = chars.Length;
            int[, ] lps = new int[length, length];
            for (int i = 0; i < length; i++) {//lps(i,j)表示s[i..j]的最长回文子序列
                lps[i, i] = 1;
            }
            for (int i = 1; i < length; i++) {
                for (int j = 0; i + j < length; j++) {
                    if (chars[j] == chars[i + j]) {
                        lps[j, i + j] = lps[j + 1, i + j - 1] + 2;
                    } else {
                        lps[j, i + j] = Math.Max (lps[j, i + j - 1], lps[j + 1, i + j]);
                    }
                }
            }
            return lps[0, length - 1];
        }
        public int LongestPalindromeSubseq1 (string s) {
            int strSize = s.Length;
            int[, ] dp = new int[strSize, strSize];
            for (int i = 0; i < strSize; i++) {//dp[i][j]代表的是字符段[i, j]最长回文子序列
                dp[i, i] = 1;
            }
            for (int len = 1; len < strSize; len++) {
                for (int i = 0; i + len < strSize; i++) {
                    int j = i + len;
                    if (s[i] == s[j]) {
                        dp[i, j] = dp[i + 1, j - 1] + 2;
                    } else {
                        dp[i, j] = Math.Max (dp[i + 1, j], dp[i, j - 1]);
                    }
                }
            }
            return dp[0, strSize - 1];
        }
        public int LongestPalindromeSubseq2 (string s) {
            int strSize = s.Length;
            int[, ] dp = new int[strSize, strSize]; //dp[i][j]代表的是字符段[i, j]最长回文子序列
            for (int i = strSize - 1; i >= 0; --i) {
                dp[i, i] = 1;
                for (int j = i + 1; j < strSize; ++j) {
                    //动态转移方程
                    if (s[i] == s[j]) {
                        dp[i, j] = dp[i + 1, j - 1] + 2;
                    } else {
                        dp[i, j] = Math.Max (dp[i + 1, j], dp[i, j - 1]);
                    }
                }
            }
            return dp[0, strSize - 1];
        }
    }
}